Data compression is used to reduce the amount of data transmitted between source and destination nodes and to further reduce the amount of memory required to store the data. Data compression is almost invariably used when transmitting a raster image between a host processor and a printer. A presently favored data compression technique for raster data operates on a "delta" basis wherein a "current" raster image row is compared with a prior image raster row and only values in the current row that differ from the prior row are transmitted. The compression operation outputs a delta compression data string which consists of a command byte followed by optional offset count bytes, optional replacement count bytes and the actual replacement data.
In FIG. 1, an exemplary delta compression data string is illustrated and in FIG. 2, details of the command byte of FIG. 1 are shown. The Command byte includes three distinct portions:
(1) a control bit which indicates whether the replacement data is encoded and what decoding scheme is utilized; PA1 (2) an offset count (four bits) which defines a number of bytes that the replacement data is offset from a current position in a seed row; and PA1 (3) a replacement count (three bits) which indicates a number of consecutive data bytes to be replaced.
If the control bit is zero, the replacement data is uncompressed or "literal" bytes from the raster data row. If the control bit equals 1, the replacement data is run length encoded.
Replacement count bits (0-2) contain a count of the number of bytes to be replaced by literal bytes following the command byte in the encoded data stream. The Offset count is the location where the replacement bytes start relative to a current position in the seed row. A current byte follows the last replacement byte or, at the beginning of a row, the left graphics margin. An offset of zero is the current byte; an offset of one is the byte following the current byte, etc. etc.
Note that the Offset count, being four bits in length, has a maximum numeric value of 15. In this prior art system, if the offset count is 15 or greater, an Offset count byte value follows the Command byte and is added to the Command byte's offset count to achieve an actual offset count. Even if the Offset count is equal to 15, an Offset count byte must follow and will indicate a value of 0, indicating that the Offset count is 15.
In similar fashion, if the Replacement count is 7, a Replacement count byte must follow the Command byte and any Offset count bytes. If the Replacement count byte is 0, then 8 bytes are replaced (i.e. bytes 0 to 7). If the Replacement count byte is 255 (i.e. a byte of all ones), another Replacement count byte follows. The last Replacement count byte is always less than 255. All Replacement count bytes are added to the Replacement count in the Command byte to obtain the total Replacement byte count. One more byte than the total Replacement count is replaced.
As can be seen from the above, the prior art compression procedure accommodates Offset count values greater than 15 and Replacement count values greater than 7 by appending Offset count bytes and Replacement count bytes, as the case may be. In fact, when the Replacement count value or the Offset count value are at their maximum (i.e., 7 and 15 respectively), count the Command byte must be followed by either an Offset byte or a Replacement count byte. Thus, while the described prior art compression procedure exhibits excellent compression characteristics, it requires specially configured hardware to handle the variable length control bytes to enable the compression action and add an undesirable cost element to the hardware.
Accordingly, it is an object of this invention to provide an improved system for data compression wherein all compression control data elements are of an identical bit size.
It is another object of this invention to provide an apparatus for data compression which employs constant size control bytes to enable lower cost compression apparatus to be configured.